/*
 * @Author: your name
 * @Date: 2020-04-12 20:56:56
 * @LastEditTime: 2020-04-12 21:47:50
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \leetcode-exercise\679-24点游戏\answer.c
 */

#define ARR_SIZE 4
#define TARGET 24
bool DFS(double *nums , int numsSize)
{
    int i;
    int j;
    int k;
    double tmp[ARR_SIZE];
    int cnt;
    /* DFS边界考虑 */
    if (numsSize == 1) {
        /* 判断是否满足24点目标值 */
        return (fabs((nums[0] - TARGET)) <= 1e-6); 
    }

    for(i = 0; i < numsSize ;i++) {
        for (j = i+1;  j < numsSize; j++) {
            /* 保留未选择的数 */
            cnt = 0;
            for ( k = 0 ; k < numsSize; k++) {
                if ( (k != i ) && (k != j)) {
                    tmp[cnt++] = nums[k];
                } 
            }
            /* 用选择出来的数据进行运算*/
            for (k = 0; k < 6; k++) {
                /* 加和乘法具有交换性，可以优化剪枝 */
                if ( k == 0 ) {
                    tmp[cnt] = nums[i] + nums[j];
                }else if ( k == 1) {
                    tmp[cnt] = nums[i] * nums[j];
                }else if ( k == 2) {
                    tmp[cnt] = nums[i] - nums[j];
                }else if ( k== 3) {
                    tmp[cnt] = nums[j] - nums[i];
                }else if ( k == 4) {
                    if (nums[j] == 0) {
                        continue;
                    }
                    tmp[cnt] = nums[i] / nums[j]; 
                } else if ( k == 5) {
                    if (nums[i] == 0) {
                        continue;
                    }
                    tmp[cnt] = nums[j] / nums[i]; 
                }
                if (DFS(tmp, cnt+1) == true) {
                    return true;
                }
            }
        }
    }
    return false;
}


bool judgePoint24(int* nums, int numsSize){
    int i ;
    double tmp[ARR_SIZE];
    /* 不满足 4个数则直接返回 false*/
    if (numsSize != ARR_SIZE) {
        return false;
    }
    /* 全部转化成double 方便分母运算*/
    for (i = 0; i < numsSize; i++){
        tmp[i] = nums[i];
    }
    return DFS(tmp, numsSize);
}